package org.hot100_3;

public class leetcode215 {
    public int findKthLargest(int[] nums, int k) {

        QuickSort(nums, 0, nums.length - 1);

        return nums[nums.length - k];
    }

    //小于piv [start.smallerIndex) = [start,smallerIndex-1]
    //等于piv [smallerIndex,biggerIndex]
    //大于piv (biggerIndex,end] = [biggerIndex+1,end]
    private void QuickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        int piv = nums[start];
        int smallerIndex = start;
        int biggerIndex = end;

        int currIndex = start + 1;

        while (currIndex <= biggerIndex) {
            if (nums[currIndex] > piv) {
                swap(nums, currIndex, biggerIndex);
                biggerIndex--;
            } else if (nums[currIndex] < piv) {
                swap(nums, currIndex, smallerIndex);
                smallerIndex++;
                currIndex++;
            } else {
                currIndex++;
            }
        }

        QuickSort(nums, start, smallerIndex - 1);
        QuickSort(nums, biggerIndex + 1, end);

    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
